package LeetCode;

import sun.nio.cs.ext.MacArabic;

import java.util.Map;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}22:08
 */
public class LeetCode121 {
    public static void main(String[] args) {
        System.out.println(new LeetCode121().maxProfit3(new int[]{7, 1, 5, 3, 6, 4}));
    }

    // 贪心算法
    public int maxProfit(int[] prices) {
        if (prices.length == 0){
            return 0;
        }
        int res = 0;
        int minValue = prices[0];
        for (int i = 1; i < prices.length; i++){
            res = Math.max(res,prices[i] - minValue);
            minValue = Math.min(minValue,prices[i]);
        }
        return res;
    }

    // 方法一：两重循环来进行排除
    public int maxProfit1(int[] prices) {
        int res = 0;
        for (int i = 0; i < prices.length; i++){
            for (int j = i; j < prices.length; j++){
                if (prices[i] < prices[j]){
                    res = Math.max(res,prices[j] - prices[i]);
                }
            }
        }
        return res;
    }

    // 动态规划1 使用两个数组，一个记录每次卖出的最大收益，一个记录每次买入的最大收益
    public int maxProfit2(int[] prices) {
        if (prices == null || prices.length == 0){
            return 0;
        }
        int len = prices.length;
        int[] sell = new int[len];
        int[] buy = new int[len];
        sell[0] = 0;// 第一天肯定只能买所以赚不到钱
        buy[0] = prices[0];
        for (int i = 1; i < len; i++){
            // 第i天卖出收益 = max(第i-1天卖出收益，当天股价 - 前一天买入的股价)
            sell[i] = Math.max(sell[i - 1],prices[i] - buy[i - 1]);
            // 更新当天买入的股价
            buy[i] = Math.min(buy[i - 1],prices[i]);
        }
        return sell[len - 1];
    }

    // 动态规划2：基于动态规划1的空间优化
    public int maxProfit3(int[] prices) {
        if (prices == null || prices.length == 0){
            return 0;
        }
        int len = prices.length;
        int sell = 0;
        int buy = prices[0];

        for (int i = 1; i < len; i++) {
            sell = Math.max(sell,prices[i] - buy);
            buy = Math.min(buy,prices[i]);
        }
        return sell;
    }

    // 只有在手上的钱才算钱，手上的钱购买当天的股票后相当于亏损。也就是说当天买的话意味着损失-prices[i]，
    // 当天卖的话意味着增加prices[i]，当天卖出总的收益就是 buy+prices[i] 。
    // 所以只要考虑当天买和之前买哪个收益最高，当天卖和之前卖哪个收益更高
    // 得状态方程：buy = max(buy, -price[i]) （注意：根据定义 buy 是负数）   sell = max(sell, prices[i] + buy)
    public int maxProfit4(int[] prices){
        if (prices.length <= 1){
            return 0;
        }
        int buy = -prices[0];
        int sell = 0;
        for (int i = 1; i < prices.length; i++){
            buy = Math.max(buy,-prices[i]);
            sell = Math.max(sell,prices[i] + buy);
        }
        return sell;
    }
}
